CS1.301 Algorithm Analysis and Design (Monsoon 2022)

Announcements

  • Teaching assistants: Posted on Moodle
  • Schedule: Lectures: Wednesday and Saturday, 10:00 – 11:25, Tutorial: Wednesday, 14:00 - 15:00
  • Classroom: H-105

Lectures

  1. Introduction to Algorithm Analysis

    • References: Chapter 2 of [1]

  2. Basic Graph Algorithms: BFS and DFS

    • References: Section 3.2 of [1]

  3. Basic Graph Algorithms: DFS (contd), and Testing bipartiteness

    • References: Sections 3.3 and 3.4 of [1]

  4. Basic Graph Algorithms: Testing bipartiteness, Search algorithms on Directed graphs

    • References: Sections 3.4 and 3.5 of [1]

  5. Basic Graph Algorithms: Directed Acyclic Graphs, and Topological sort

    • References: Sections 3.5 and 3.6 of [1]

  6. Greedy Algorithms: Shortest paths

    • References: Section 4.4 of [1]

  7. Greedy Algorithms: Minimum spanning trees

    • References: Sections 4.5 and 4.6 of [1]

  8. Greedy Algorithms: Huffman coding

    • References: Section 4.8 of [1]

  9. Greedy Algorithms: Huffman coding (contd.), and Interval scheduling

    • References: Sections 4.8 and 4.1 of [1]

  10. Divide and Conquer: Merge sort, Karatsuba’s integer multiplication, Strassen’s matrix multiplication

    • References: Sections 5.1, 5.2 and 5.5 of [1]

  11. Divide and Conquer: Discrete Fourier Transform

    • References: Section 5.5 of [1]

  12. Divide and Conquer: Closest pair of points

    • References: Section 5.4 of [1]

  13. Review

  14. Dynamic Programming: Fibonacci, Longest Increasing Subsequence

    • References: Sections 3.2 and 3.6 of [4]

  15. Dynamic Programming: Interval scheduling

    • References: Sections 6.1 and 6.2 of [1]

  16. Dynamic Programming: Subset problem, 0-1 Knapsack, Matrix Chain Multiplication

    • References: Section 6.4 of [1], and section 2.8 of [5]

  17. Dynamic Programming: All pairs shortest paths

    • References: Section 6.8 of [1]

  18. Network Flows I

    • References: Section 7.1 of [1]

  19. Network Flows II

    • References: Sections 7.1 and 7.2 of [1]

  20. Network Flows III

    • References: Section 7.1 of [1]

  21. Network Flows IV

    • References: Section 7.1 of [1]

  22. Computational Efficiency, and Intractability I

    • References: Chapter 12 of [4]

  23. Computational Efficiency, and Intractability II

    • References: Chapter 12 of [4]

  24. Computational Efficiency, and Intractability III

    • References: Chapter 12 of [4]

  25. Computational Efficiency, and Intractability IV

    • References: Chapter 12 of [4]

References

  1. J. Kleinberg, and E. Tardos (2005), Algorithm Design, Pearson (Addison Wesley).
  2. T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms (third edition, 2009), MIT press and McGraw Hill.
  3. S. Dasgupta, C. Papadimitrou, and U. Vazirani, Algorithms (first edition, 2006), McGraw Hill Education.
  4. J. Erickson, Algorithms (first edition, 2019).
  5. A. Aho, J. Hopcraft, and J. Ullman, Design and Analysis of Algorithms (1974), Addison Wesley.